export default class Graph {
    private arr!: number[];
    private edge!: number[][];

    constructor(arr: number[]) {
        this.arr = arr;
        this.edge = Array(arr.length);
        for (let i = 0; i < arr.length; i++) {
            this.edge[i] = Array(arr.length).fill(0);
        }
        // this.edge = Array(8).fill(new Array(8).fill(0));
    }

    public insertEdge(x: number, y: number) {
        this.edge[x][y] = 1;
        this.edge[y][x] = 1;
    }

    public getEdge() {
        return this.edge;
    }

    private getFirst(index: number) {
        for (let i = 0; i < this.arr.length; i++) {
            if (this.edge[index][i] === 1) {
                return i;
            }
        }
        return -1;
    }

    private getNext(v1: number, v2: number) {
        for (let i = v2 + 1; i < this.arr.length; i++) {
            if (this.edge[v1][i] === 1) {
                return i;
            }
        }
        return -1;
    }

    public dfs() {
        const { length } = this.arr;
        const isVisited: boolean[] = Array(length).fill(false);
        const res: number[] = [];
        for (let i = 0; i < length; i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                res.push(this.arr[i]);
                let v1 = i;
                let vertex = this.getFirst(v1);
                while (vertex !== -1) {
                    if (!isVisited[vertex]) {
                        v1 = vertex;
                        isVisited[vertex] = true;
                        res.push(this.arr[vertex]);
                        vertex = this.getFirst(vertex);
                    } else {
                        vertex = this.getNext(v1, vertex);
                    }
                }
            }
        }
        return res;
    }

    public bfs() {
        const { length } = this.arr;
        const isVisited: boolean[] = Array(length).fill(false);
        const res: number[] = [];
        for (let i = 0; i < length; i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                res.push(this.arr[i]);
            }
            for (let j = i + 1; j < length; j++) {
                if (!isVisited[j]) {
                    isVisited[j] = true;
                    res.push(this.arr[j]);
                }
            }
        }
        return res;
    }
}